package mid;

public class a990_等式方程的可满足性 {
    public boolean equationsPossible(String[] equations) {
        int len=equations.length;
        UFDS ufds = new UFDS(26);
        for(int i =0;i<len;i++){
            char c1=equations[i].charAt(0);
            char c2=equations[i].charAt(3);
            if(equations[i].charAt(1)!='!'){
                ufds.union(c1-'a',c2-'a');
            }
        }
        for (int i = 0; i < len; i++) {
            char c1 = equations[i].charAt(0);
            char c2 = equations[i].charAt(3);
            if (equations[i].charAt(1) == '!'&&ufds.find(c1-'a')==ufds.find(c2-'a')){
                return false;
            }
        }
        return true;
    }


    class UFDS {
        int[] father;

        public UFDS(int n) {
            father = new int[n];
            for (int i = 0; i < n; i++) {
                father[i] = i;
            }
        }

        public int find(int i) {
            if (i != father[i]) {
                return find(father[i]);
            }
            return father[i];
        }

        public boolean union(int x, int y) {
            int fx = find(x);
            int fy = find(y);
            if (fy == fx) return false;
            father[fy] = fx;
            return true;
        }
    }
}
